package com.markus.code.二叉树.leetcode;

import java.util.HashMap;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/12 21:44
 * todo: 从中序和后序遍历序列构造二叉树
 */
public class LeetCode_106 {
    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    private HashMap<Integer,Integer> indexMap;
    private int[] postorder;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0 || inorder.length != postorder.length){
            return null;
        }
        this.postorder = postorder;
        indexMap = new HashMap<>();
        for (int i=0;i<inorder.length;i++){
            indexMap.put(inorder[i],i);
        }
        return buildNode(0,postorder.length-1,0,inorder.length-1);
    }
    private TreeNode buildNode(int aL,int aR,int iL,int iR){
        if (aL > aR){
            return null;
        }
        int rootValue = postorder[aR];
        int index = indexMap.get(rootValue);
        TreeNode root = new TreeNode(rootValue);
        root.left = buildNode(aL,aL+index-iL-1,iL,index-1);
        root.right = buildNode(aL+index-iL,aR-1,index+1,iR);
        return root;
    }
    private void printTree(TreeNode root){
        if (root != null){
            System.out.print(root.val+" ");
            printTree(root.left);
            printTree(root.right);
        }
    }
}
